Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Реалізація алгоритмів пошуку на графічному процесорі

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2024
Тип роботи:
Розрахункова робота
Предмет:
СП
Група:
ІУСм-12

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Розрахункова робота з дисципліни «Проблемно-орієнтовані обчислювальні комплекси та системи» на тему «Реалізація алгоритмів пошуку на графічному процесорі» ЗМІСТ І. Бінарний пошук 3 1.1. Бінарний пошук у CPU 3 1.2. Бінарний пошук у GPU 4 ІІ. Реалізація алгоритму SSSP на GPU 11 ІІІ. Реалізація алгоритму BFS на GPU 18 СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 23 І. Бінарний пошук Бінарний пошук у CPU Класична реалізація бінарного пошуку у CPU досить проста в програмуванні. Інші модифікації і поліпшення можуть виявитися корисними лише за певних умов. Буде розглянуто загальний випадок. По-друге: максимум за величину порядку ln2 N порівнянь буде знайдено шуканий ключ (або установлено, що його немає в таблиці). Не багато інших алгоритмів зможуть потягатися з такою швидкодією. І так маємо в самому гіршому випадку ln2 N порівнянь. Правда алгоритм застосуємо лише для відсортованого списку. Реалізація на CPU має наступний вигляд: __host__ void searchCPU ( float * data, int * result ) { int x = 16777200; // шуканий елемент int i = 0; // ліва границя масиву int j = 16 * 1024 * 1024; // права границя масиву int k = 0; while ( i <= j ) { k = i + (j - i) / 2 ; if ( data[k] < x ) { i = k + 1; } else if ( data[k] > x ) { j = k - 1; } else { result[0] = data [k]; result[1] = k; break; } } } Як можна побачити, дійсно нічого складного. Даний алгоритм значно перевершує по швидкодії простий лінійний пошук (у багато сотень разів), реалізований навіть на GPU, адже для лінійного пошуку маємо N порівнянь в гіршому випадку. Але, як вже говорилося вище, він можливий лише для відсортованого списку (про сортування трохи нижче). До речі кажучи, цей алгоритм набагато стійкіший, оскільки для нього практично не має значення в якій частині списку перебуває елемент, тоді як для лінійного – від цього безпосередньо залежить час пошуку. Але це в реалізації на CPU! На GPU для лінійного пошуку маємо протилежний випадок тобто досить стійкий алгоритм, тому безліч потоків може майже одночасно охопити різні ділянки списку. Бінарний пошук у GPU Графік порівняння продуктивності для CPU і GPU, зображений на рисунку 1. / Рисунок 1. Графік порівняння продуктивності для CPU і GPU Як бачимо з графіка, швидкодія GPU починає перевершувати свій аналог на CPU лише на певній позначці, тобто при досить великих обсягах динних. Спробуємо реалізувати бінарний пошук для GPU і підтвердити або спростувати дані у вищевказаному графіку. Але яким чином розділити обчислення між потоками? Перша думка була найпростіша. Розділити весь список на рівні ділянки, в кожній ділянці виконувати бінарний пошук. Потрібно зауважити, що чим менше потоків, тим швидше виконується програма, тобто її швидкодія найбільша при одному потоці. Алгоритм такий: ділимо весь список на кількість потоків, Кожен потік дивиться один елемент і порівнює його з шуканим. Якщо це шуканий елемент чудово. Якщо поточний елемент менший, запам'ятовуємо його як нижню межу. Якщо більший запам'ятовуємо як верхню межу. Кожен з потоків знайде свій елемент більший або менший шуканого, а нам потрібні тільки граничні елементи, між якими лежить шуканий, отже, потрібно серед менших елементів залишити максимум, а серед більших мінімум. Далі повторюємо процедуру, але вже не для всього списку а для нових його меж. Повторюємо доти поки або не знайдемо елемент, або кількість елементів між нижньою і верхньою межею стане меншою кількості потоків. У такому випадку для решти елементів застосовуємо будь-який інший алгоритм, наприклад однопотоковий бінарний пошук. Розглянемо приклад. Нехай маємо 2 048 елементів і 32 потоки. Для зручності індекси елементів у масиві і їх значення будемо вважати однаковими. Шукаємо, скажімо, елемент під номером 65 рівний 65. І так перший крок. Для кожного потоку дивимося кожен 32 елемент. тобто перший...
Антиботан аватар за замовчуванням

08.12.2015 09:12

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини